1. Technical Field of the Invention
The invention relates generally to communication systems; and, more particularly, it relates to decoding of signals within such communication systems.
2. Description of Related Art
Data communication systems have been under continual development for many years. One such type of communication system that has been of significant interest lately is a communication system that employs turbo codes. Another type of communication system that has also received interest is a communication system that employs LDPC (Low Density Parity Check) code. A primary directive in these areas of development has been to try continually to lower the error floor within a communication system. The ideal goal has been to try to reach Shannon's limit in a communication channel. Shannon's limit may be viewed as being the data rate to be used in a communication channel, having a particular SNR (Signal to Noise Ratio), that achieves error free transmission through the communication channel. In other words, the Shannon limit is the theoretical bound for channel capacity for a given modulation and code rate.
LDPC code has been shown to provide for excellent decoding performance that can approach the Shannon limit in some cases. For example, some LDPC decoders have been shown to come within 0.3 dB (decibels) from the theoretical Shannon limit. While this example was achieved using an irregular LDPC code of a length of one million, it nevertheless demonstrates the very promising application of LDPC codes within communication systems.
Typical encoding of LDPC coded modulation signals is performed by generating a signal that includes symbols each having a common code rate and being mapped to a singular modulation. That is to say, all of the symbols of such an LDPC coded modulation signal have the same code rate and the same modulation (the same constellation having a singular mapping). Oftentimes, such prior art encoding designs are implemented as to maximize the hardware and processing efficiencies of the particular design employed to generate the LDPC coded modulation signal having the single code rate and single modulation for all of the symbols generated therein.
With respect to decoding of such LDPC coded modulation signals, decoding is most commonly performed based on a bipartite graph of a given LDPC code such that the graph includes both bit nodes and check nodes. The I, Q (In-phase, Quadrature) values associated with received symbols are associated with a symbol node, and that symbol node is associated with corresponding bit nodes. Bit metrics are then calculated for the individual bits of the corresponding symbols, and those bit metrics are provided to the bit nodes of the bipartite graph of the given LDPC code. Edge information corresponding to the edges (e.g., edge messages) that interconnect the bit nodes and the check nodes is calculated, and appropriately updated, and communicated back and forth between the bit nodes and the check nodes during iterative decoding of the LDPC coded signal.
A common approach to performing bit decoding of such LDPC coded signals is to use the prior art a posteriori probability (APP) decoding approach of a graph code using so-called sum product algorithm (SPA). The following references described this prior art SPA decoding approach.
[1] R. Gallager, Low-Density Parity-Check Codes, Cambridge, Mass.: MIT Press, 1963.
[2] M. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, and V. Stemann, “Practical Loss-Resilient Codes”, Proc. 29th Symp. on Theory of Computing, 1997, pp. 150-159.
[3] D. J. C. MacKay, “Good error correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, Vol. 45, pp. 399-431, March 1999.
[4] G. D. Forney, “Codes on graphs: normal realizations,” IEEE Trans. Inform. Theory, Vol. 47, pp. 520-548, February 2001.
Using the prior art SPA approach to decoding LDPC coded signals, the check node is estimated with a sum and a product of the estimation that is obtained from bit nodes. This combination of the sum and product terms is why this prior art approach is commonly referred to as the SPA approach (e.g., sum and product). Within this most common prior art SPA approach to bit decoding of LDPC coded signals, the approach operates by calculating APP of the LDPC graph code. This involves employing a number of different sum of terms functions (e.g., Σ), and then multiplying each of those respective sum of terms functions together using a product of terms functions (e.g., Π). This combination of performing the sum of terms functions and product of terms functions during each and every edge message updating iteration is extraordinarily computationally intensive. When implementing this approach to decoding LDPC coded signals, the hardware required to support and perform this combination of sum of terms functions and product of terms functions is very costly in terms of processing resources, memory, memory management concerns, etc.
In the following, a brief introduction of this SPA approach to decoding LDPC coded signals is presented.
Define the metric of bit node i by metrici(a)=Pr(yi|vi=a). To initialize the decoding processing, define
            bit      e      0        ⁡          (      a      )        =                    metric                  b          ⁡                      (            e            )                              ⁡              (        a        )              .  Then the check node estimate and the bit node estimate are performed as follows:
1. Check estimate: for every edge compute
                                                                        check                e                n                            ⁡                              (                a                )                                      =                        ⁢                                          Pr                ⁡                                  (                                                                                    c                                                  c                          ⁡                                                      (                            e                            )                                                                                              =                                                                        0                          ❘                                                      v                                                          b                              ⁡                                                              (                                e                                )                                                                                                                                    =                        a                                                              ,                    y                                    )                                            =                                                ∑                                      u                    ∈                                                                  U                        e                                            ⁡                                              (                        a                        )                                                                                            ⁢                                                      ∏                                          ∫                                              ∈                                                                                                            E                              c                                                        ⁡                                                          (                                                              c                                ⁡                                                                  (                                  e                                  )                                                                                            )                                                                                ∖                                                      {                            e                            }                                                                                                                                ⁢                                                                          ⁢                                                            bit                                              e                        ′                                                                    n                        -                        1                                                              ⁡                                          (                                                                        u                          b                                                                          (                          f                          )                                                                    )                                                                                                    ;                ⁢                                  ⁢        where        ⁢                                  ⁢                                            U              e                        ⁡                          (              a              )                                =                                    {                                                                    u                    1                                    ∈                                      {                                          0                      ,                      1                                        }                                                  ,                                                                                                    (                                                  t                          ,                                                                                    c                              ⁡                                                              (                                e                                )                                                                                      ∈                                                                                          E                                c                                                            ⁡                                                              (                                e                                )                                                                                                                                    )                                            ∖                                              {                        e                        }                                                              ❘                                                                  ∑                        t                                            ⁢                                                                                          ⁢                                              u                        t                                                                              =                  a                                            }                        .                                              (                  EQ          ⁢                                          ⁢          1                )            
2. Bit estimate: For every edge e compute
                                                                                          bit                  e                  n                                ⁡                                  (                  a                  )                                            =                            ⁢                              Pr                ⁡                                  (                                                                                    v                                                  b                          ⁡                                                      (                            e                            )                                                                                              =                                            ⁢                                                                        a                          ❘                                                      c                                                          c                              ⁡                                                              (                                                                  e                                  ′                                                                )                                                                                                                                    =                                                ⁢                        0                                                              ,                                          f                      ∈                                                                                                    E                            v                                                    ⁡                                                      (                                                          b                              ⁡                                                              (                                e                                )                                                                                      )                                                                          ∖                                                  {                          e                          }                                                                                      ,                    y                                    )                                                                                                                                                              bit                    e                    n                                    ⁡                                      (                    a                    )                                                  =                                ⁢                                                                            metric                                              b                        ⁡                                                  (                          e                          )                                                                                      ⁡                                          (                      a                      )                                                        ⁢                                                            ∏                                              ∫                                                  ∈                                                                                                                    E                                v                                                            ⁡                                                              (                                                                  b                                  ⁡                                                                      (                                    e                                    )                                                                                                  )                                                                                      ∖                                                          {                              e                              }                                                                                                                                            ⁢                                                                  check                        f                        n                                            ⁡                                              (                        a                        )                                                                                                        ⁢                                                                                                      (                  EQ          ⁢                                          ⁢          2                )            
The estimate at the n-th iteration is as follows:
            P              (        n        )              ⁡          (                        b          i                =                  a          ❘          y                    )        =                    metric        i            ⁡              (        a        )              ⁢                  ∏                  e          ∈                                    E              b                        ⁡                          (              i              )                                          ⁢                          ⁢                                    check            e            n                    ⁡                      (            a            )                          .            
In the application of graph codes on a communication system, the operation of the decoding is oftentimes actually implemented in the logarithm domain (e.g., the log domain). Multiplications may be implemented in the log domain using addition, and divisions may be implemented in the log domain using subtraction. Therefore, when using SPA approach to decoding LDPC coded signals, the logarithm of the sum of several values has to be carried out. This computational processing of summing over several values, when implemented in the log domain, may significantly increase the complexity of the hardware that is employed to implement a decoder that performs this SPA approach.
As can clearly be seen, there is a need in the art to provide a new means by which LDPC coded signals may be decoded that is less computationally intensive. As such, a less computationally intensive approach could potentially be implemented more simplistically in hardware. If a less computationally intensive approach could be achieved, then a device implementing such approach could provide for a significant degree of savings in many measurable operational parameters including processing resources, memory, memory management concerns, etc.